﻿#define _CRT_SECURE_NO_WARNINGS 1
//给你一个 正 整数 num ，输出它的补数。补数是对该数的二进制表示取反。
//int findComplement(int num){
//	long tmp = 1;
//	while (num >= tmp)
//	{
//		tmp <<= 1;
//	}
//	return (tmp - 1 - num);
//}








//给定只含 "I"（增大）或 "D"（减小）的字符串 S ，令 N = S.length。
//返回 [0, 1, ..., N] 的任意排列 A 使得对于所有 i = 0, ..., N - 1，都有：
//如果 S[i] == "I"，那么 A[i] < A[i + 1]
//如果 S[i] == "D"，那么 A[i] > A[i + 1]
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/di-string-match
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
///**
//* Note: The returned array must be malloced, assume caller calls free().
//*/
//int* diStringMatch(char * s, int* returnSize){
//	int len = strlen(s);
//	int* a = (int*)malloc(sizeof(int)*(len + 1));
//	*returnSize = len + 1;
//	int i = 0;
//	int max = 1;
//	int mid = -1;
//	a[0] = 0;
//	for (i = 0; i<len; i++)
//	{
//		if (s[i] == 'I')
//		{
//			a[i + 1] = max++;
//		}
//		else
//		{
//			a[i + 1] = mid--;
//		}
//	}
//	for (i = 0; i <= len; i++)
//	{
//		a[i] += -mid - 1;
//	}
//	return a;
//}







//给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
//
//在 S 上反复执行重复项删除操作，直到无法继续删除。
//
//在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
//
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/remove-all-adjacent-duplicates-in-string
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//char * removeDuplicates(char * s){
//	int len = strlen(s);
//	char*a = (char*)malloc(sizeof(char)*len);
//	int i = 0;
//	int sz = 0;
//	for (i = 0; i<len; i++)
//	{
//		if (sz>0 && a[sz - 1] == s[i])
//		{
//			sz--;
//		}
//		else
//		{
//			a[sz++] = s[i];
//		}
//	}
//	a[sz] = '\0';
//	return a;
//}








//给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
//char ret(char*s, int mid, int max)
//{
//	max -= 1;
//	char tmp = 0;
//	while (mid<max)
//	{
//		tmp = s[mid];
//		s[mid] = s[max];
//		s[max] = tmp;
//		max--;
//		mid++;
//	}
//	return s;
//}
//char * reverseWords(char * s){
//	int i = 0;
//	int mid = 0;
//	int max = 0;
//	while (s[i] != '\0')
//	{
//		if (s[i] == ' ')
//		{
//			ret(s, mid, max);
//			mid = max + 1;
//		}
//		max++;
//		i++;
//	}
//	ret(s, mid, max);
//	return s;
//}







//给你两个长度相同的整数数组 target 和 arr 。
//每一步中，你可以选择 arr 的任意 非空子数组 并将它翻转。你可以执行此过程任意次。
//如果你能让 arr 变得与 target 相同，返回 True；否则，返回 False 。
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/make-two-arrays-equal-by-reversing-sub-arrays
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//bool canBeEqual(int* target, int targetSize, int* arr, int arrSize){
//	int i = 0;
//	int falg = 0;
//	int j = 0;
//	if (targetSize == arrSize)
//	{
//		for (i = 0; i<targetSize; i++)
//		{
//			falg = 0;
//			for (j = 0; j<arrSize; j++)
//			{
//				if (target[i] == arr[j])
//				{
//					falg = 1;
//					arr[j] = 0;
//					break;
//				}
//			}
//			if (falg == 0)
//			{
//				return false;
//			}
//		}
//	}
//	return true;
//}










//给你一个整数数组 nums 。数组中唯一元素是那些只出现 恰好一次 的元素。
//请你返回 nums 中唯一元素的 和 。
//int sumOfUnique(int* nums, int numsSize){
//	int i = 0;
//	int j = 0;
//	int count = 0;
//	int flag = 0;
//	for (i = 0; i<numsSize; i++)
//	{
//		flag = 0;
//		for (j = 0; j<numsSize; j++)
//		{
//			if (nums[i] == nums[j] && i != j)
//			{
//				flag = 1;
//				break;
//			}
//		}
//		if (flag == 0)
//		{
//			count += nums[i];
//		}
//	}
//	return count;
//}







//给你一个 m * n 的矩阵 grid，矩阵中的元素无论是按行还是按列，都以非递增顺序排列。
//请你统计并返回 grid 中 负数 的数目。
//int countNegatives(int** grid, int gridSize, int* gridColSize){
//	int count = 0;
//	int i = 0;
//	int j = 0;
//	for (i = 0; i<gridSize; i++)
//	{
//		for (j = 0; j<*gridColSize; j++)
//		{
//			if (grid[i][j]<0)
//			{
//				count++;
//			}
//		}
//	}
//	return count;
//}








//给你一个字符串 s，它由数字（'0' - '9'）和 '#' 组成。我们希望按下述规则将 s 映射为一些小写英文字符：
//字符（'a' - 'i'）分别用（'1' - '9'）表示。
//字符（'j' - 'z'）分别用（'10#' - '26#'）表示。 
//返回映射之后形成的新字符串。
//题目数据保证映射始终唯一。
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/decrypt-string-from-alphabet-to-integer-mapping
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//char * freqAlphabets(char * s){
//	int len = strlen(s);
//	char* str = (char*)malloc(len*sizeof(char));
//	int i = 0;
//	int j = 0;
//	for (i = 0; i<len;)
//	{
//		if (i + 2<len&&s[i + 2] == '#')
//		{
//			str[j++] = ((s[i] - '0') * 10 + s[i + 1] - '1') + 'a';
//			i += 3;
//		}
//		else
//		{
//			str[j++] = s[i] - '1' + 'a';
//			i++;
//		}
//	}
//	str[j] = '\0';
//	return str;
//}








//编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
//不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
//你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
//void reverseString(char* s, int sSize){
//	int max = sSize - 1;
//	int mid = 0;
//	char tmp = 0;
//	while (mid <= max)
//	{
//		tmp = s[max];
//		s[max] = s[mid];
//		s[mid] = tmp;
//		max--;
//		mid++;
//	}
//	return s;
//}







//给你一个仅由数字 6 和 9 组成的正整数 num。
//你最多只能翻转一位数字，将 6 变成 9，或者把 9 变成 6 。
//请返回你可以得到的最大数字。
//int maximum69Number(int num){
//	int tmp = 0;
//	int count = 0;
//	int n = num;
//	while (n)
//	{
//		count++;
//		if (n % 10 == 6)
//		{
//			tmp = count;
//		}
//		n /= 10;
//	}
//	return num + 3 * pow(10, tmp - 1);
//}